/**
 * @Author liangzai
 * @Description:
 */
public class BinaryTree {
    public TreeNode find(TreeNode root,char val){
        if(root == null){
            return null;
        }
        if(root.val == val){
            return root;
        }
        TreeNode retL = find(root.left,val);
        if(retL != null){
            return retL;
        }
        TreeNode retR = find(root.right,val);
        if(retR != null){
            return retR;
        }
        return null;
    }

    public boolean isSameTree(TreeNode p ,TreeNode q){
        if(q!=null && p==null || q==null && p!=null){
            return false;
        }
        if(q==null && p==null){
            return true;
        }
        if(q.val == p.val){
            return true;
        }

        return isSameTree(p.left,q.left) && isSameTree(p.right,p.left);
    }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null){
            return false;
        }
        if(isSameTree(root,subRoot) ){
            return true;
        }
        // if(isSubtree(root.left,subRoot)) {
        //     return true;
        // }
        // if(isSubtree(root.right,subRoot)) {
        //     return true;
        // }
        // return false;
        return isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
    }

    public TreeNode mirrorTree(TreeNode root) {
        if(root == null){
            return null;
        }
        TreeNode tmp = root.right;
        root.right = root.left;
        root.left = tmp;
        mirrorTree(root.right);
        mirrorTree(root.left);
        return root;
    }

    private boolean checkLeafNode(TreeNode left,TreeNode right){
        if(left !=null && right == null || left==null && right != null){
            return false;
        }

        if(left == null && right == null){
            return true;
        }

        if(left.val != right.val){
            return false;
        }
        return checkLeafNode(left.left,right.right) && checkLeafNode(left.right, right.left);
    }

    public boolean checkSymmetricTree(TreeNode root) {
        if(root == null){
            return true;
        }
        return checkLeafNode(root.left, root.right);
    }

    private int getMaxDepth2(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftlong = getMaxDepth2(root.left);
        int rightlong = getMaxDepth2(root.right);

        return leftlong>rightlong?leftlong+1:rightlong+1;
    }
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        int a = getMaxDepth2(root.left);
        int b = getMaxDepth2(root.right);

        // if((a>=0 ? a : -a) >= 2){
        //     return false;
        // }
        return Math.abs(a-b)<2 && isBalanced(root.left) && isBalanced(root.right);
    }


}
